package leetcode_400;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *IsSubsequence_392 判断一个字符串是否是另一个字符串的子序列
 *describe:用双指针扫描 AC 78%
 *2018年7月13日 下午5:21:53
 */
public class IsSubsequence_392 {
	public static void main(String[] args) {
		IsSubsequence_392 test=new IsSubsequence_392();
		System.out.println(test.isSubsequence("abc", "ahbgdc"));
		System.out.println(test.isSubsequence("axc", "ahbgdc"));
	}
	
	
	/**
	 * describe:用hash记录某个元素出现的位置 但是最后一个用例超时 
	 * 2018年7月13日 下午5:23:03
	 */
	public boolean isSubsequence(String s, String t) {
	       Map<Character,List<Integer>> hash= new HashMap<Character,List<Integer>>();
	       for(int i=0;i<t.length();++i){
	    	   char now=t.charAt(i);
	    	   List<Integer> list=hash.get(now);
	    	   if(list==null) {
	    		   List<Integer> newList=new ArrayList<Integer>();
	    		   newList.add(i);
	    		   hash.put(now, newList);
	    	   }
	    	   else {
	    		   list.add(i);
	    	   }
	       }
	       int index=-1;
	       for(int i=0;i<s.length();++i) {
	    	   char now=s.charAt(i);
	    	   List<Integer> list=hash.get(now);
	    	   if(list==null||list.size()==0)
	    		   return false;
	    	   boolean flag=false;
	    	   while(list.size()!=0) {//循环条件是list里面有值 退出有两个情况 的确找到了合适的字符 退完了还没有找到符
	    		   int first=list.get(0);
	    		   if(first<index) {
	    			   list.remove(0);
	    			   continue;
	    		   }
	    		   else {
	    			   list.remove(0);
	    			   index=first;
	    			   flag=true;
	    			   break;
	    		   }
	    	   }
	    	   if(!flag)
	    		   return false;
	    	   
	       }
	       return true;
    }
	
	 /**
	 * describe:双指针扫描 AC 78%
	 * 2018年7月13日 下午6:28:46
	 */
	public boolean isSubsequence1(String s, String t) {
		 int i=0,j=0;
		 while(i<s.length()&&j<t.length()) {
			 char charS=s.charAt(i);
			 while(j<t.length()&&t.charAt(j)!=charS)
				 ++j;//去找
			 if(j==t.length())//显然没找到
				 return false;
			 ++i;
			 ++j;
		 }
		 return true;
	 }
}
